Problem
Code

Yesterday I wrote another post I named "How to tackle simulations too big to simulate". And then, today is exactly that: a simulation too big simulate.

Part one is a warmup, we'll skip right over that^[1]; part 2 is a classic case of what I described in my post. It's very similar to a bunch of other solutions: You find a cycle, use it to skip most of the several million iterations you're meant to calculate, and then simulate the couple leftover steps.

pub fn two(input: &str) -> crate::Result<i32> {
    let width = input.lines().next().map(str\:\:len).unwrap_or(0);
    let height = input.lines().count();
    let mut seen = HashMap::new();

    let mut map = Map {
        data: input.bytes().filter(|c| !c.is_ascii_control()).collect(),
        width: width as i32,
        height: height as i32,
    };

    seen.insert(map.data.clone(), 0);
    for i in 1.. {
        spin_cycle(&mut map);

        if let Some(v) = seen.insert(map.data.clone(), i) {
            let left = (1000000000 - i) % (i - v);
            for _ in 0..left {
                spin_cycle(&mut map);
            }

            let items = map.data.iter().enumerate();
            return Ok(items
                .map(|(i, t)| match t {
                    b'O' => map.height - i as i32 / map.width,
                    _ => 0,
                })
                .sum());
        }
    }

    unreachable!()
}

I treat the map as a flat 1D array indexed by y * width + x. It's equivalent to having a nested array, but in some cases less annoying to deal with.

Here I remember every single full map until I find one that repeats (in Rust, inserting into a HashMap returns the old value if there was one already). Then we can skip a bunch of iterations using the fact that the map repeats.

For example, if we had to do 100 steps, but step 15 was a repetition of step 4, we'd know that the map is the exact same at steps 4, 15, 26, 37, 48, 59, 70, 81, 92. Since we're already at step 15, we can simply pretend we're at step 92, and do 8 more steps manually to reach 100 total.

Same idea, just much bigger numbers involved.

Update a couple hours later

This is gonna start happening now, as I stare at my working solution throughout the day and start seeing little improvements I can make.

No need to re-simulate the final steps after skipping cycles

Going back to my smaller example (100 steps, step 15 repeats step 4), I originally said we can just "simulate the couple leftover steps". We've already simulated steps 4 through 15, and because step 92 would be the same as 4, step 100 would be the same as step 12... which we already have.

for step in 1.. {
	spin_cycle(&mut map);

	let repeat = seen.insert(map.data.clone(), step);
	if let Some(repeat) = repeat {
		let left = (1000000000 - step) % (step - repeat);
		let (data, _) = seen.into_iter().find(|(_, v)| *v == repeat + left).unwrap();

		let weight = |(i, tile): (usize, &u8)| match tile {
			b'O' => map.height - i as i32 / map.width,
			_ => 0,
		};

		return Ok(data.iter().enumerate().map(weight).sum());
	}
}

I also factored out the weight calculation into a little lambda. Reads neater this way I think.